package com.lagou.assignment2;

/**
 *
 */
public class GetBestGoldMining {


//    我们把金矿数量设为n，工人数量设为w，金矿的含金量设为数组g[ ]，金矿所需开采人数设为数组p[ ]. 设F(n, w)为n个金矿、w个工人时的最优收益函数，那么状态转移方程式如下。
//
//    F(n,w) = 0 (n=0或w=0)
//
//    问题边界，金矿数为0或工人数为0的情况。
//
//    F(n,w)= F(n-1,W) (n≥1, w<p[n-1])
//
//    当所剩工人不够挖掘当前金矿时，只有一种最优子结构。
//
//    F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n≥1, w≥p[n-1])
//
//    在常规情况下，具有两种最优子结构(挖当前金矿或不挖当前金矿)。

    /**
     * 获得金矿最优收益
     *
     * @param w 工人数量 10
     * @param n 可选金矿数量 5
     * @param p 金矿开采所需的工人数量 {5,5,3,4,3}
     * @param g 金矿储量 {400,500,200,300,350}
     * @return
     */
    //递归进行求解
    public static int getBestGoldMining(int w, int n, int[] p, int[] g) {
        if (w == 0 || n == 0) {
            return 0;
        }
        if (w < p[n - 1]) {
            return getBestGoldMining(w, n - 1, p, g);
        }
        return Math.max(getBestGoldMining(w, n - 1, p, g), getBestGoldMining(w - p[n - 1], n - 1, p, g) + g[n - 1]);
    }


    public static void main(String[] args) {
        int w = 10;
        int[] p = {5, 5, 3, 4, 3};
        int[] g = {400, 500, 200, 300, 350};
        System.out.println("最优收益：" + getBestGoldMining(w, g.length, p, g));
    }
}

